package com.chenken;


/**
 *	冒泡排序
 *	用前一个元素与后一个元素比较，如果前一个元素较大，将2个元素交换位置
 *  每进行一轮，数组中的最大元素都会被挑选出来，放到最后，
 *  所以，每进行一轮，最后面的元素都不需要扫描，外层循环要i--
 *  
 */
public class BubbleSort2<T extends Comparable<T>> extends Sort<T>{

	/**
	 * 优化1
	 * 如果一轮扫描下来，都没有任何元素交换过位置，说明数组已经是排好序了，就不用再循环了
	 * 对于一个完全无序的数组来说，这个优化没有意义，反而会增加复杂度
	 * @param arrays
	 */
	@Override
	public void sort() {
		for(int end = arrays.length-1;end>0;end--) {
			boolean sorted = false;
			for(int begin = 1;begin<=end;begin++) {
				if(compare(arrays[begin],arrays[begin-1])<0) {
					swap(begin,begin-1);
					sorted = true;
				}
			}
			if(!sorted) break;
		}
	}
	
}
